package DataStructure.tree;

import java.util.Arrays;
import java.util.Stack;

/**
 * 236. 二叉树的最近公共祖先 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
 * 题目简述：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 * todo 整理解法
 */
public class LowestCommonAncestor {

    public static void main(String[] args) {
        TreeNode tree = RestoreBinaryTree.restoreLevelTraversal(Arrays.asList(2, null, 1));
        new LowestCommonAncestor().lowestCommonAncestor(tree, tree, tree.right);
    }


    /**
     * 思路一：最近公共祖先存在两种情况：1. p或q本身就是 2. p和q分别在一个节点的两棵子树中，这种节点只存在一个就是最近公共祖先
     * 因此采用递归后续遍历，递归函数体功能为判断当前树中是否包含p或q。其中额外判断root是否为p或q以应对情况1，并判断左右子树是否分别包含p和q以应对情况2，这两种情况都更新ans
     * 由于后续遍历覆盖赋值最后ans肯定是在高处的祖先，因此无论是第一种还是第二种情况在低处的错误赋值都不影响
     */
    TreeNode ans=null;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root,p,q);
        return ans;
    }

    /**
     * 递归函数体定义：判断root树中是否包含节点p者q
     */
    public boolean dfs(TreeNode root,TreeNode p,TreeNode q){
        if (root == null) {
            return false;
        }
        boolean left=dfs(root.left,p,q);
        boolean right=dfs(root.right,p,q);

        //判断root是否为p或q（情况1），或者左右子树中分别包含了p和q（情况2），满足则更新ans
        if (root==p || root==q || (left&&right)){
            ans=root;
            return true;
        }

        return left || right; //当前子树是否包含p或q
    }

    /**
     * 思路二：采用后序遍历。当遍历到p或q其中一个时，则公共祖先必然在其上层，将cf指向其父节点。
     * 当遍历到cf但还没遍历到另外一个节点时，说明以cf为根节点的子树虽然包含了一个节点，但没有包含另外一个节点，则公共祖先必然还在cf上层，将cf指向其父节点，即在更高一层的子树中进行查找
     * 遍历到另一个节点后，则以cf为根节点的子树为包含两个节点的最小子树，即cf为最近公共祖先
     */
    boolean findP = false, findQ = false;
    TreeNode cf = null;
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            if(stack.peek().right == null) {
                root = popFind(stack, p, q);
                if (root == cf) return cf;
                while(!stack.isEmpty() && stack.peek().right == root) {
                    root = popFind(stack, p, q);
                    if (root == cf) return cf;
                }
            }
            root = !stack.isEmpty() ? stack.peek().right : null;
        }
        return cf;
    }

    /**
     * 若p,q都已找到，则当前cf即为最近公共祖先，将其返回
     */
    public TreeNode popFind(Stack<TreeNode> stack, TreeNode p, TreeNode q) {
        TreeNode t = stack.pop();
        if (t == p) findP = true;
        if (t == q) findQ = true;
        if(findP && findQ) {
            return cf;
        }
        if (t == p || t == q || t == cf)
            cf = stack.peek();
        return t;
    }

    /**
     * 思路二递归版
     */
    TreeNode p ,q;
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        this.p = p;
        this.q = q;
        dfs(root, root.left);
        dfs(root, root.right);
        return cf;
    }

    public void dfs(TreeNode r, TreeNode rc) {
        if (rc == null) return;
        dfs(rc, rc.left);
        dfs(rc, rc.right);
        if (rc == p) findP = true;
        if (rc == q) findQ = true;
        if(findP && findQ) return;
        if (rc == p || rc == q || rc == cf)
            cf = r;
    }
}
